package com.ctrip.study.algorithm.pratice;

import java.util.Queue;
import java.util.Stack;

import org.eclipse.jetty.util.ArrayQueue;
import org.junit.Test;

import junit.framework.TestCase;

/**
 * 输入一颗二元树，从上往下按层打印树的每个结点，
 * 同一层中按照从左往右的顺序打印.
 */
public class TreeSortPrint extends TestCase{
	
	@Test
	public void test(){
		Tree tree = constructTree();
		print(tree.root);
	}

	private void print(Node root) {
		Queue<Node> queue = new ArrayQueue<>();
		queue.add(root);
		while(!queue.isEmpty()){
			Node currentNode = queue.poll();
			System.out.println(currentNode);
			if(currentNode.left != null){
				queue.add(currentNode.left);
			}
			if(currentNode.right != null){
				queue.add(currentNode.right);
			}
		}
	}

	public Tree constructTree() {
		Tree tree = new Tree();
		tree.insert(10);
		tree.insert(6);
		tree.insert(14);
		tree.insert(4);
		tree.insert(8);
		tree.insert(12);
		tree.insert(16);
		return tree;
	}

	private class Node {
		public int key;
		public Node left;
		public Node right;

		public Node pre;
		public Node next;

		public Node(int key) {
			this.key = key;
		}

		@Override
		public String toString() {
			return "Node [key=" + key + "]";
		}

	}

	private class Tree {
		private Node root;

		public void insert(int key) {
			if (root == null) {
				root = new Node(key);
			} else {
				Node current = root;
				Node parent = null;
				Boolean isLeft = true;
				while (current != null) {
					parent = current;
					if (key < current.key) {
						current = current.left;
						isLeft = true;
					} else {
						current = current.right;
						isLeft = false;
					}
				}
				if (isLeft) {
					parent.left = new Node(key);
				} else {
					parent.right = new Node(key);
				}
			}
		}

	}
	
}
